This document relates to an analog belief propagation processor.
“Belief Propagation” (BP) is an efficient approach to solving statistical inference problems. The approach exploits underlying structure of a network of stochastic elements and its constraints and Bayesian laws of probabilities to find the most optimal set of valid outputs that satisfy constrains and network structure requirements.
Belief Propagation includes a class of techniques for performing statistical inference using a system model that is in the form of a graph. The term “graph” here refers to the mathematical definition of a graph, which represents the connectedness of a set of abstract objects. The objects are often referred to as “nodes” and the connections between objects are often referred to as “edges.” One common type of graph used in such models is referred to as a “factor graph.” In a factor graph (a particular style of factor graph called a “Forney factor graph”) the nodes represents statistical relationships between values, which are represented as edges. Other types of graphs, such as Bayesian networks, and Markov random fields are also commonly used for statistical inference.
Examples of Belief Propagation approaches operate by passing messages between nodes in the graph, where each message represents a summary of the information known by that node through its connections to other nodes. Such approaches are known by various names, including belief propagation, probability propagation, message passing, and summary-product algorithms, among others. Particular forms of these approaches include sum-product, max-product, and min-sum.
A large variety of approaches to coding, signal processing, and artificial intelligence may be viewed as instances of the summary-product approach (or belief/probability propagation approach), which operates by message passing in a graphical model. Specific instances of such approaches include Kalman filtering and smoothing, the forward backward algorithm for hidden Markov models, probability propagation in Bayesian networks, and decoding algorithms for error correcting codes such as the Viterbi algorithm, the BCJR algorithm, and the iterative decoding of turbo codes, low-density parity check codes, and similar codes.
Graphs on which belief propagation may operate include two types: graphs with loops (cyclic graphs) and graphs with no loops (acyclic graphs). Graphs with no loops are also known as “trees.” Belief propagation procedures differ fundamentally between these two types of graphs. For a tree, belief propagation approach can proceed in a well-defined order with a well-defined number of steps to compute the result. And assuming ideal computation, this result is always known to be correct. For a graph with loops, on the other hand, belief propagation approaches are generally iterative, meaning the same set of computations must be repeated successively until a result is reached. In this case, the computation typically converges to a useful result, but does not always do so. In some cases, the computation may not converge to a single result, or if it does, the result in some cases is inaccurate. For a cyclic graph, the performance of belief propagation can depend on the order in which the computations are performed, which is known as the message passing ‘schedule.’
In one particular application mentioned above, Belief Propagation has been adopted as an efficient method of implementing decoders for various forward error correcting codes. In this case BP uses structure of the code and constraints to infer the correct valid codeword from the input codeword that contains noise, for instance, with each element (e.g., bit) of the input codeword being represented as a distribution rather than a discrete value. In some implementations of Belief Propagation for forward error correction a Digital Signal Processor is used to perform various arithmetic computations required by the algorithm with all the statistical data being processed in digital format.
Observing the fact that “soft”—probabilistic data is continuous in nature, i.e., represented by real values in a finite interval, it is possible to implement belief propagation algorithm using analog electrical circuits. Since only one signal is associated with the unit of statistical data rather than multiple signals for different digits (e.g., binary digits, bits) of the digital signal representing the same data, the savings in hardware and power dissipation can be very significant.
Several architectures had been proposed that utilize analog circuits to perform efficient decoding of various codes, including convolutional codes, Low Density Parity Check Codes (LDPC) or linear block codes. These include analog implementations that use a so-called full flat architecture, where each input data symbol is associated with dedicated computing element.